package demo.practice.bfs;

public class P117 {

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(7);
        P117 p117 = new P117();
        p117.connect(root);

    }

    public Node connect(Node root) {
        if(root == null)
            return null;

        Node head = new Node(0);
        Node headCur = head;
        Node cur = root;

        while(true){
            while(cur != null){
                if(cur.left != null){
                    headCur.next = cur.left;
                    headCur = headCur.next;
                }

                if(cur.right != null){
                    headCur.next = cur.right;
                    headCur = headCur.next;
                }

                cur = cur.next;
            }

            cur = head.next;
            head.next = null;    //sanity clean
            headCur = head;

            if(cur == null)
                break;
        }

        return root;
    }
}
